package 分类.一维动规;

import java.util.Arrays;

public class 零钱兑换 {
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        memo=new int[amount+1];
        Arrays.fill(memo,666);
        return dp(coins,amount);
    }

    int dp(int[] coins,int amount){
       if(amount==0) return 1;
       if(amount<0) return -1;
       if(memo[amount]!=666){
           return memo[amount];
       }
       int res=Integer.MAX_VALUE;
        for (int coin : coins) {
            int subProblem=dp(coins,amount-coin);
            if(subProblem==-1) continue;
            res=Math.min(res,subProblem+1);
        }
        memo[amount]=(res==Integer.MAX_VALUE?-1:res);
        return res;
    }

    //dp递归方程
    public int coinChange1(int[] coins,int amount){
        int[] dp=new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for (int i=0;i<=amount;i++){
            for (int coin : coins) {
                if(i-coin<0){
                    continue;
                }
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}
